package com.fyl.leetcode.DFS;

/**
 * @author:fyl
 * @date 2021/5/18 10:29
 * @Modified By:
 * @Modified Date:
 * @Description: 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 * 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
 * 输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
 * 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的'O'都不会被填充为'X'。 任何不在边界上，
 * 或不与边界上的'O'相连的'O'最终都会被填充为'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 *
 * 对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O；
 * 最后我们遍历这个矩阵，对于每一个字母：
 * 如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
 * 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。
 *
 */
public class Solve {
    private final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int m;
    int n;

    public void solve(char[][] board) {
        //处理上下左右边界
        n = board.length;
        if (n == 0) {
            return;
        }
        m = board[0].length;
        /*     不能这样写，需要排除已经处理过的左右边界
         *     for (int i = 0; i < n; i++) {
         *             dealBorder( i, 0,board);
         *             dealBorder( i, m - 1,board);
         *             dealBorder(0, i,board);
         *             dealBorder( n - 1, i,board);
         *         }
         */
        //处理左右边界
        for (int i = 0; i < n; i++) {
            dealBorder( i, 0,board);
            dealBorder( i, m - 1,board);
        }
        //处理上下边界，i = 1; i < m - 1;是排除已经处理过的左右边界
        for (int i = 1; i < m - 1; i++) {
            dealBorder(0, i,board);
            dealBorder( n - 1, i,board);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j]=='O'){
                    board[i][j] = 'X';
                }
                if (board[i][j]=='1'){
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dealBorder(int i, int j, char[][] board) {
        if (i < 0 || j < 0 || i >= n || j >= m || board[i][j] != 'O'){
            return;
        }
        board[i][j] = '1';
        for (int[] dir : direction) {
            dealBorder(i+dir[0],j+dir[1],board);
        }
    }
}
